Batch 3 - Class 247 - State Diagrams and Turing Machines 2

• Has a notion of states as described above
• There may be several inputs/actions that happen when in a state
• On each of those inputs, the state changes (and well, there might be an output)
• Lets draw the state diagram of lifecycle of a chicken

• Every state must have an output and transition for every input.

• Discuss the programming of FSM through rules (if-then-else) statements. Need to store the state in a given variable.
• Discuss alternate programming style by storing the entire state machine in a table, and looking it up, depending on current state and input.
• This program could potentially solve any problem which can be modeled as a FSM, just by changing the table
• Can we make a counting FSM? So given a set of inputs, it counts how many there are
• Simply have states labeled for each counting step, like "zero", "one", "two" and so on, and on each input go one forward
• What are the problems?
• Much bigger than what a program looks like. Because number of states can be large
• But fundamentally, finite. You can't draw a FSM for arbitarily large counting.

• Ask kids if they know what Turing machines are
• Why - how do we know which problems are solvable or not? Does it depend on the computer we use? Does it depend on the power of the computer? Does it depend on the programming language?
• Introduce a notion of a theoretical computer. Simple, standardized, and useful as a theoretical construct to analyze programs rather than to use physically. A Turing machine introduces a tape on which stuff can be read (initial input), and written back. The states are just left or right movement.
• Lets take a look at an example
• Alphabet 0,1,A,X,#
• The initial tape could look like 

• The tape head scans the input symbol on current location, overwrites it with another symbol, and moves left or right. For example, we could go to 

• The control unit (which determines what to do) is a FSM. The states are Left, Right, or Halt. For example

• Lets try to run this machine for a few steps (start with 3 A's)

• What is this machine doing?
• It is converting unary to binary - in some sense it is counting the A's
• Where is the final result stored? 
• When we drew the FSM, we didn't say where the inputs were coming from. And we couldn't write anything. 
• What was the equivalent of writing back in FSM - "state transition". What if we can store all that output on the tape and keep the state machine simple - like "increment the number on the tape"
• But more importantly, if we can have an infinitely long tape, then we don't have to have a very large FSM. Turing maching gives us that.
• What is the "state" of the turing machine system at any point in time?
• Lets think about some more examples.
• Copy: converts 111 into 1110111 - assume zeros on each end infinitely.
• Start from left end and overwrite the first 1 with 0
• Move right till it encounters first 0 (skip over initial string of 1s)
• Move right till it encounters first 0 (skip over copied string of 1s)
• Write 1, and move left back over the middle zero and then to the first zero (over the initial string of 1s)
• Rewrite the erased 1, and move right - if there is a 1 here, then overwrite it
• Can you think about how you would add two unary numbers?
• Some interesting facts
• Turing machine is complete - anything that it can't compute is generally not computble
• The problem of whether a particular program will HALT is not computable
• The problem of whether a particular program will print a particular strong is not computable

• (CombProbs Problem 52) Can you arrange numbers 1..9 in a circle so that sum of two neighbors is never divisible by 3, 5 or 7
• Answer: 5,6,2,9,4,7,1,3,8,(5) - One way to do this is to figure out all combinations which are "allowed", i.e. not divisible by 3,5,7. Then start to work with constraints like number 2 can only go with 6 and 9, and build from there. Number 4 can only go with 9 and 7, so that extends the sequence to 6,2,9,4,7, and so on.